package 笔试.Shopee;

import java.util.ArrayList;
import java.util.PriorityQueue;

public class 波动序列 {
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     * <p>
     * <p>
     * 计算摆动序列的最长子序列的长度
     *
     * @param nums int整型 一维数组 摆动序列
     * @return int整型
     */
    public int wiggleMaxLength(int[] nums) {
        ArrayList<Integer> cur = new ArrayList<>();
        PriorityQueue<ArrayList<Integer>> res = new PriorityQueue<>(((o1, o2) -> -o1.size() + o2.size()));
        dfs(nums, cur, res, 0);
        for (ArrayList<Integer> re : res) {
            if (checkNums(re)) {
                return re.size();
            }
        }
        return 0;
    }

    private boolean checkNums(ArrayList<Integer> re) {
        boolean flag = re.get(0) < re.get(1);
        for (int i = 1; i < re.size() - 1; i++) {
            if (re.get(0) < re.get(1) && flag && re.get(i) > re.get(i + 1)) {
                flag = false;
            } else if (!flag && re.get(i) < re.get(i + 1)) {
                flag = true;
            } else {
                return false;
            }
        }
        return true;
    }

    private void dfs(int[] nums, ArrayList<Integer> cur, PriorityQueue<ArrayList<Integer>> res, int index) {
        if (index > nums.length) {
            return;
        }
        if (!cur.isEmpty()) {
            res.add(new ArrayList<>(cur));
        }
        for (int i = index; i < nums.length; i++) {
            cur.add(nums[i]);
            dfs(nums, cur, res, i + 1);
            cur.remove(cur.size() - 1);
        }
    }

    public static void main(String[] args) {
        波动序列 solution = new 波动序列();
        int[] nums = {1, 7, 4, 9, 2, 5};
        System.out.println(solution.wiggleMaxLength(nums));
    }
}
